﻿
using System;
using System.Runtime.CompilerServices;

namespace PhraseCorrector.SpellCore
{
    /// <summary>
    /// 提供优化方法以计算两个字符串之间的 Levenshtein 距离比较的类。
    /// </summary>
    /// <remarks>
    /// 版权 ©2015-2018 SoftWx, Inc.
    /// 创建高度优化的编辑距离函数的灵感来源于 Sten Hjelmqvist 的“快速且内存高效”算法，
    /// 详细描述见 http://www.codeproject.com/Articles/13525/Fast-memory-efficient-Levenshtein-algorithm
    /// Levenshtein 算法计算两个字符串之间的编辑距离度量，即所需的插入、删除和替换操作次数，
    /// 以将一个字符串转换为另一个字符串。该值将 >= 0，其中 0 表示完全相同的字符串。
    /// 比较区分大小写，例如，“Fred”和“fred”的距离为 1。
    /// 优化算法的详细描述见我的帖子：
    /// http://blog.softwx.net/2014/12/optimizing-levenshtein-algorithm-in-c.html
    /// 更多一般信息见 http://en.wikipedia.org/wiki/Levenshtein_distance
    /// 本类中的方法不是线程安全的。如果需要线程安全的方法，请使用 Distance 类中的静态版本。
    /// </remarks>
    public class Levenshtein : IDistance
    {
        // 存储计算编辑距离的基础成本数组
        private int[] baseChar1Costs;

        ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        /// <summary>创建 Levenshtein 的新实例。</summary>
        public Levenshtein()
        {
            baseChar1Costs= new int[0];
        }

        ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        /// <summary>使用指定的预期最大字符串长度创建 Levenshtein 的新实例。</summary>
        /// <remarks>通过指定最大预期字符串长度，可以实现更好的内存效率。</remarks>
        /// <param name="expectedMaxStringLength">将传递给 Levenshtein 方法的字符串的预期最大长度。</param>
        public Levenshtein(int expectedMaxStringLength)
        {
            this.baseChar1Costs= new int[expectedMaxStringLength];
        }

        ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// 比较两个字符串的长度，并交换它们的值。
        /// </summary>
        /// <param name="string1">第一个字符串</param>
        /// <param name="string2">第二个字符串</param>
        /// <returns>返回一个元组，元组中的第一个元素是较短的字符串，第二个元素是较长的字符串。</returns>
        private static (string string1, string string2) ChangeValue(string string1, string string2)
        {
            // 如果第一个字符串的长度大于第二个字符串，则交换两个字符串的值
            // 否则，保持两个字符串的原始顺序不变
            return string1.Length > string2.Length
                ? (string2, string1)
                : (string1, string2);
        }

        ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        /// <summary>计算并返回两个字符串之间的 Levenshtein 编辑距离。</summary>
        /// <remarks>https://github.com/softwx/SoftWx.Match
        /// 此方法不是线程安全的。</remarks>
        /// <param name="string1">要比较的一个字符串。</param>
        /// <param name="string2">要比较的另一个字符串。</param>
        /// <returns>如果字符串相同则返回 0，否则返回一个正值，该值的大小随着字符串之间差异的增加而增加。</returns>
        public double Distance(string string01, string string02)
        {
            if (string01== null) return (string02 ?? "").Length;
            if (string02== null) return string01.Length;

            // 如果字符串长度不同，确保较短的字符串在 string1 中。这可以通过在主要处理期间仅循环内部循环来提高速度。
            (string string1, string string2)= ChangeValue(string01, string02);
            // 确定可以忽略的公共后缀和/或前缀
            return Distance1(string1, string2);
        }
        
        ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// 计算两个字符串之间的距离值。
        /// </summary>
        /// <param name="string1">第一个字符串。</param>
        /// <param name="string2">第二个字符串。</param>
        /// <returns>返回计算出的距离值。</returns>
        public double Distance1(string string1, string string2)
        {
            // 确定可以忽略的公共后缀和/或前缀
            Helpers.PrefixSuffixPrep(string1, string2, out int len1, out int len2, out int start);

            // 如果第一个字符串为空，则直接返回第二个字符串的长度
            return (len1== 0)
                ? len2
                : Distance(string1, string2, len1, len2, start, (this.baseChar1Costs= (len2 <= this.baseChar1Costs.Length) ? this.baseChar1Costs : new int[len2]));
        }
        
        ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        /// <summary>计算并返回两个字符串之间的 Levenshtein 编辑距离。</summary>
        /// <remarks>https://github.com/softwx/SoftWx.Match
        /// 此方法不是线程安全的。</remarks>
        /// <param name="string1">要比较的一个字符串。</param>
        /// <param name="string2">要比较的另一个字符串。</param>
        /// <param name="maxDistance">感兴趣的最远距离。</param>
        /// <returns>-1 表示距离大于 maxDistance；0 表示字符串相同；否则返回一个正值，该值随字符串差异增大而增加。</returns>
        public double Distance(string string1, string string2, double maxDistance)
        {
            if (string1== null || string2== null) return Helpers.NullDistanceResults(string1, string2, maxDistance);
            if (maxDistance <= 0) return (string1== string2) ? 0 : -1;
            maxDistance= Math.Ceiling(maxDistance);
            int iMaxDistance= (maxDistance <= int.MaxValue) ? (int)maxDistance : int.MaxValue;

            // 如果字符串长度不同，确保较短的字符串在 string1 中。这可以通过在主要处理期间仅循环内部循环来提高速度。
            if (string1.Length > string2.Length) { var t= string1; string1= string2; string2= t; }
            if (string2.Length - string1.Length > iMaxDistance) return -1;

            // 确定可以忽略的公共后缀和/或前缀
            Helpers.PrefixSuffixPrep(string1, string2, out int len1, out int len2, out int start);
            if (len1== 0) return (len2 <= iMaxDistance) ? len2 : -1;

            if (iMaxDistance < len2)
                return Distance(string1, string2, len1, len2, start, iMaxDistance,
                    (this.baseChar1Costs= (len2 <= this.baseChar1Costs.Length) ? this.baseChar1Costs : new int[len2]));

            return Distance(string1, string2, len1, len2, start,
                (this.baseChar1Costs= (len2 <= this.baseChar1Costs.Length) ? this.baseChar1Costs : new int[len2]));
        }

        ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        /// <summary>Levenshtein 算法的核心实现。</summary>
        /// <remarks>https://github.com/softwx/SoftWx.Match</remarks>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        internal static int Distance(string string1, string string2, int len1, int len2, int start, int[] char1Costs)
        {
            for (int j= 0; j < len2;) char1Costs[j]= ++j;
            int currentCharCost= 0;
            if (start== 0)
            {
                for (int i= 0; i < len1; ++i)
                {
                    int leftCharCost, aboveCharCost;
                    leftCharCost= aboveCharCost= i;
                    char char1= string1[i];
                    for (int j= 0; j < len2; ++j)
                    {
                        currentCharCost= leftCharCost; // 对角线上的代价（替换）
                        leftCharCost= char1Costs[j];
                        if (string2[j] != char1)
                        {
                            // 替换，除非满足以下两个条件之一
                            if (aboveCharCost < currentCharCost) currentCharCost= aboveCharCost; // 删除
                            if (leftCharCost < currentCharCost) currentCharCost= leftCharCost; // 插入
                            ++currentCharCost;
                        }
                        char1Costs[j]= aboveCharCost= currentCharCost;
                    }
                }
            }
            else
            {
                for (int i= 0; i < len1; ++i)
                {
                    int leftCharCost, aboveCharCost;
                    leftCharCost= aboveCharCost= i;
                    char char1= string1[start + i];
                    for (int j= 0; j < len2; ++j)
                    {
                        currentCharCost= leftCharCost; // 对角线上的代价（替换）
                        leftCharCost= char1Costs[j];
                        if (string2[start + j] != char1)
                        {
                            // 替换，除非满足以下两个条件之一
                            if (aboveCharCost < currentCharCost) currentCharCost= aboveCharCost; // 删除
                            if (leftCharCost < currentCharCost) currentCharCost= leftCharCost; // 插入
                            ++currentCharCost;
                        }
                        char1Costs[j]= aboveCharCost= currentCharCost;
                    }
                }
            }
            return currentCharCost;
        }

        ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        /// <summary>接受最大距离参数的 Levenshtein 算法核心实现。</summary>
        /// <remarks>https://github.com/softwx/SoftWx.Match</remarks>
        internal static int Distance(string string1, string string2, int len1, int len2, int start, int maxDistance, int[] char1Costs)
        {

            int i, j;
            for (j= 0; j < maxDistance;) char1Costs[j]= ++j;
            for (; j < len2;) char1Costs[j++]= maxDistance + 1;

            int lenDiff= len2 - len1;
            int jStartOffset= maxDistance - lenDiff;
            int jStart= 0;
            int jEnd= maxDistance;
            int currentCost= 0;

            if (start== 0)
            {
                for (i= 0; i < len1; ++i)
                {
                    char char1= string1[i];
                    int prevChar1Cost, aboveCharCost;
                    prevChar1Cost= aboveCharCost= i;

                    // 不需要查看超出右下对角线 - 最大距离的窗口（右下对角线是 i - lenDiff）以及左上对角线 + 最大距离的窗口（左上对角线是 i）
                    jStart += (i > jStartOffset) ? 1 : 0;
                    jEnd += (jEnd < len2) ? 1 : 0;

                    for (j= jStart; j < jEnd; ++j)
                    {
                        currentCost= prevChar1Cost; // 对角线上的代价（替换）
                        prevChar1Cost= char1Costs[j];
                        if (string2[j] != char1)
                        {
                            // 替换，除非满足以下两个条件之一
                            if (aboveCharCost < currentCost) currentCost= aboveCharCost; // 删除
                            if (prevChar1Cost < currentCost) currentCost= prevChar1Cost; // 插入
                            ++currentCost;
                        }
                        char1Costs[j]= aboveCharCost= currentCost;
                    }
                    if (char1Costs[i + lenDiff] > maxDistance) return -1;
                }
            }
            else
            {
                for (i= 0; i < len1; ++i)
                {
                    char char1= string1[start + i];
                    int prevChar1Cost, aboveCharCost;
                    prevChar1Cost= aboveCharCost= i;

                    // 不需要查看超出右下对角线 - 最大距离的窗口（右下对角线是 i - lenDiff）以及左上对角线 + 最大距离的窗口（左上对角线是 i）
                    jStart += (i > jStartOffset) ? 1 : 0;
                    jEnd += (jEnd < len2) ? 1 : 0;

                    for (j= jStart; j < jEnd; ++j)
                    {
                        currentCost= prevChar1Cost; // 对角线上的代价（替换）
                        prevChar1Cost= char1Costs[j];
                        if (string2[start + j] != char1)
                        {
                            // 替换，除非满足以下两个条件之一
                            if (aboveCharCost < currentCost) currentCost= aboveCharCost; // 删除
                            if (prevChar1Cost < currentCost) currentCost= prevChar1Cost; // 插入
                            ++currentCost;
                        }
                        char1Costs[j]= aboveCharCost= currentCost;
                    }
                    if (char1Costs[i + lenDiff] > maxDistance) return -1;
                }
            }
            return (currentCost <= maxDistance) ? currentCost : -1;
        }
    }
}

